#include <stdio.h>

// wezly
typedef struct Node *link;
struct Node { // trzyczesciowa struktura wezla
  char item;
  link l;
  link r;
};
typedef struct Node node;
link T; // dowiazanie do korzenia
void node_print(node ); // wydruk informacji w wezle
void node_visit(link ); // wizytowanie wezla
void dummy_ins(node ); // wstawienie atrapy
link node_insleft(node , link ); // wstawienie wezla do drzewa binarnego po lewej stronie wskazywanej przez t
link node_insright(node , link ); // wstawienie wezla do drzewa binarnego po prawej stronie wskazywanej przez t
link tree_example(); // przykladowe drzewo binarne zapamietane na piechote

// drzewo
void tree_show(link , int ); // wydruk drzewa w terminalu
void tree_traverse(link ); // przechodzenie drzewa metoda inorder

int main() 
{
  link root = tree_example();
  tree_traverse(root);
  return 0;
}

// funkcje dla wezlow
void dummy_ins(node a) 
{
  link t;
  t = (node*)malloc(sizeof(node ));
  t->item = a.item;
  t->l = t;
  t->r = t;
  T = t;
} 

link node_insright(node a, link t) 
{
  link p;
  p = (node*)malloc(sizeof(node ));
  p->item = a.item;
  t->r = p;
  p->r = NULL;
  p->l = NULL;
  return p;
}

link node_insleft(node a, link t) 
{
  link p;
  p = (node*)malloc(sizeof(node ));
  p->item = a.item;
  t->l = p;
  p->l = NULL;
  p->r = NULL;
  return p;
}

void node_visit(link t) 
{
  printf("%c ", t->item);
}

// funkcje dla drzewa
link tree_example()
{
  int  n;
  node a; 
  link now, templ, tempr;
  n = 10;
  a.item = ' ';
  dummy_ins(a);
  a.item = 'A';
  now = node_insleft(a, T);
  a.item = 'B';
  templ = now;
  now = node_insleft(a, now);
  a.item = 'D';
  templ = now;
  now = node_insleft(a, now);
  a.item = 'C';
  now = T->l;
  now = node_insright(a, now);
  a.item = 'E';
  templ = now;
  now = node_insleft(a, now);
  tempr = now;
  a.item = 'G';
  now = tempr;
  now = node_insright(a, now);
  a.item = 'F';
  now = templ;
  now = node_insright(a, now);
  tempr = now;
  a.item = 'J';
  now = tempr;
  now = node_insright(a, now);
  a.item = 'H';
  now = tempr;
  now = node_insleft(a, now);
  return T->l;
}

void tree_print(node a, int h) 
{
  int i;
  for(i = 0; i < h; i++) printf(" ");
  printf("%c\n", a.item);
}

void tree_show(link t, int h)
{
  node a;
  a.item = '*';
  if (t == 0) {
    tree_print(a, h);
    return;
  };
  tree_show(t->r, h + 1);
  a.item = t->item;
  tree_print(a, h);
  tree_show(t->l, h + 1);
}

void tree_traverse(link t) 
{
  if (t == 0) return;
  tree_traverse(t->l);
  node_visit(t);
  tree_traverse(t->r);
}

